class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ans;
        stack<TreeNode*> st;
        st.push(root);
        while (!st.empty())
        {
            TreeNode* top = st.top();
            if (!top)
            {
                st.pop();
                continue;
            }
            ans.push_back(top->val);
            st.pop();

            st.push(top->right);
            st.push(top->left);
        }
        return ans;
    }
};